package com.wujunshen.algorithm.leetcode.dynamic.programming;

/**
 * @author frank woo(吴峻申) <br>
 * email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/8/11 14:30<br>
 */
public class 编辑距离 {
    public int minDistance(String word1, String word2) {
        int n = word1.length();
        int m = word2.length();
        //添加空格
        word1 = ' ' + word1;
        word2 = ' ' + word2;
        int[][] f = new int[n + 1][m + 1];

        for(int i = 0;i <= n;i++) {
            //i次删除
            f[i][0] = i;
        }
        for(int i = 0;i <= m;i++) {
            //i次删除 word1 -> word2
            f[0][i] = i;
        }
        for(int i = 1;i <= n;i++) {
            for(int j = 1;j <= m;j++) {
                //添加或者删除
                f[i][j] = Math.min(f[i - 1][j] + 1, f[i][j - 1] + 1);
                if(word1.charAt(i) == word2.charAt(j)) {
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1]);
                } else {
                    //替换
                    f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + 1);
                }
            }
        }
        return f[n][m];
    }
}
